Zurück zu den Suchalgorithmen. Wir haben das letzte Mal angefangen mit den

D-Vitam Kanker Algorithmen und haben gesagt, die arbeiten nach dem Prinzip,

teile das Problem, löse die Teilprobleme, kombiniere die Teillösungen. Und wir haben

zwei Vorgehensweisen kennengelernt, wobei wir das letzte Mal die erste

kennengelernt haben, das war die Easy Split Hard Join, das heißt, das Teilen

ist trivial und die Arbeit wird beim Zusammenbauen gemacht. Heute werden wir

kennenlernen, den Hard Split Easy Join, das Aufteilen, da wird die ganze Arbeit

gemacht und beim Zusammenbauen, da ist die Arbeit schon getan.

Vielleicht noch mal zur Erinnerung, was war jetzt anhand des Beispieles des

Easy Split Hard Join? Ich habe hier die Sortieraufgabe.

Entschuldigung.

Dankeschön.

Entschuldigung.

Ja, ich habe die Sortieraufgabe, ich habe eine Datenstruktur und ich möchte

sortieren. Was ich mache, ist, dass ich immer in der

Hälfte aufschneide und wenn es noch keine triviale Datenstruktur ist, dann

schneide ich das auf, also ich fange an und schneide in der Hälfte auf, diese

noch nicht trivial, dann schneide ich die auf, dann schneide ich die auf. So und

jetzt habe ich alle Datenstrukturen geteilt und einelementige Listen sind

sortiert und jetzt kommt der Hard Join. Ich fange jetzt an und tue die

Teilstrukturen wieder zusammenbauen und beim Zusammenbauen sortiere ich. Also ich

fange an und sortiere

die beiden, das L und E wird sortiert, dann ist diese Teilliste sortiert, die, die

und die, dann nehme ich die nächste Ebene, Sie sehen, diese wird hier mit ein

sortiert, die beiden werden zu dem sortiert, das wird zusammengebaut und

dann wird die ganze Liste abgebaut. Sie sehen, die Arbeit wird beim

Zusammenholen gemacht.

Dann und wir kommen jetzt zum Sortieren, zum Sortieren durch zerlegen, das, den

sogenannten Quick Sort Algorithmus, DD ist die folgende, ich zerlege die

Gesamtaufgabe in zwei Sortieraufgaben, nämlich einen linken Teil, in dem ich nur

kleine Werte habe, einen rechten Teil, in dem ich nur große Werte habe und das

stellen wir dadurch her, dass wir zunächst einmal einfach die kleinen

Werte nach links schmeißen, die großen Werte nach rechts, unabhängig davon, wie

sie sortiert sind. Damit haben wir eine Position und von der auf können wir

sagen, links davon sind die kleinen, rechts davon sind die großen Werte und

das machen wir dann immer weiter rekursiv, ja und wenn wir dann in der

Situation sind, dass auch für die trivialen Listen immer das linke

sozusagen das kleinere ist, dann ist die Zusammenfügung trivial, weil durch das

platztauschen ist die Konkatenation dieser Teillösungen ja bereits sortiert.

Diese Quick Sort Algorithmus hat die Eigenschaft, dass er keinen zusätzlichen

Speicherplatz benötigt, er sortiert in place, was auch insbesondere bei

Feldern sehr interessant ist und er hat die Komplexitätsklasse O von n log n,

aber dazu sage ich am Ende noch was. Also wir haben eine Reihung von Elementen und

wir haben eine Ordnung drauf und wir haben einen Ausschnitt m, n von Indizes und

innerhalb dieser Indizes, da haben wir ein sogenanntes Pivot-Element und dieses

Pivot-Element, das nehmen wir jetzt her und sorgen dafür, dass alle Elemente, die

kleiner sind als dieses Pivot-Element, links von ihm sind und alle die größer

sind rechts. Die Vorgehensweise ist also die folgende, wir wählen uns so ein Pivot-

Element und entfernen das da draus und sorgen jetzt dafür, dass es eine

Teilfolge gibt, die mit dem ursprünglichen Index m anfängt und bei i minus 1